/*
题目: 全排列Ⅱ
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class PermuteⅡ {
    //总共三种去重方式
    //1. 排好序, 但是不用每个元素都选:
    // if (i != start && nums[i] == nums[i - 1])
    //2. 排好序, 而且每个元素都要选, 这时候如果同一层的两个连续的相等, 就去重
    // if (i > 0 && nums[i] == nums[i - 1])

    List<List<Integer>> result = new ArrayList<> ();
    boolean[] used = null;
    int n = 0;

    public List<List<Integer>> permuteUnique(int[] nums) {
        n = nums.length;
        used = new boolean[n]; //表示下标为i的元素是否使用过

        Arrays.sort(nums);
        backTrack(nums, new Stack<> ());
        return result;
    }

    private void backTrack(int[] nums, Stack<Integer> path) {
        if (path.size() == n) {
            result.add(new ArrayList<> (path));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            used[i] = true;
            path.push(nums[i]);
            backTrack(nums, path);
            path.pop();
            used[i] = !used[i];
        }
    }
}
